%	\chapter{机器学习基础}
\section{基本术语}
机器学习的基本对象是数据集(data set)，一个数据集中的每条记录是关于一个对象的一组描述，称为示例(instance)或样本(sample)$X_i$。事实上，可以认为其为服从总体分布的一列随机向量，而具体的取值就是观察值，这与数理统计的定义是一致的(见参数估计一章的数理统计概念一节)。

随机向量的每一个维度$X^j$称为属性(attribute)或特征(feature)，每一个分量观察值$x_i^j$称为属性值(attribute value)。随机向量的取值范围是属性空间(attribute spase)或样本空间(sample)或输入空间。一个示例$X_i$作为一个随机向量的观察值，也称为特征向量(feature vector)。注意这个特征向量与线代中的特征向量(characteristic vector)是不一样的。

从数据中学得模型的过程称为学习(learning)或训练(training)。学习所用的数据为训练数据(training data)，每个样本$X_i$称为训练样本(training sample)，训练样本组成的集合$\left\{X_i\right\}$为训练集(training set)。学得的数据存在某种规律，称为假设(hypothesis)。与潜在规律对应的真实规律，称为真相或真实(ground truth)。有时模型也叫学习器(learner)。

对应于一系列的属性值，我们需要一个预测的结果。一组属性映射$x_i^j$到一个结果$y_i$，这种结果称为标记(label)，这种映射称为预测(prediction)。将样本属性和标记放在一组$(x_i^j,y_i)$，构成样例(example)。标记所有的取值范围称为标记空间(label space)或输出空间。

标记$Y$同样是一个随机变量，但其与前面的样本$X$之间显然不能是独立的，不然学习它们之间的关系就无从谈起了。标记$Y$是离散型随机变量，就称这种学习任务是分类(classification)；如果标记$Y$是连续型随机变量，就称这种学习任务是回归(regression)。当然，我们都知道计算机中不存在真正的连续变量，因此只要是标记为浮点数的，或者取值足够多、足够稠密的，都可以视作回归。

有时，无需标记，只对数据作聚类(clustering)，把分开的每组数据称为簇(cluster)，这种簇可能对应一些潜在的概念的划分，但这些概念我们事先不知道。这种无标记的学习称为无监督学习(unsupervised learning)；相应地有标记的学习称为有监督学习(supervised learning)。

如果模型能在训练集以外的数据，也就是全样本空间里的数据都具有良好的适用性，就称其具有泛化(generalization)能力。一般而言，与数理统计中相同，样本$X_i$与总体$X$之间是独立同分布的，训练样本越多，关于总体的信息就越多，根据大数定律，越有可能通过学习获得具有强泛化能力的模型。

归纳(induction)和演绎(deduction)是科学推理的两大手段，前者是从特殊到一般的泛化(generalization)过程，后者是从一般到特殊的特化(specialization)过程。从样例学习的过程显然是归纳的。狭义的归纳学习需要习得概念(concept)，但当今应用甚少；广义的归纳学习就是我们所见的从样例中学习。

如果只是记住训练集中的样本，然后一一作匹配，这样显然就不具备泛化能力了，如果测试集中出现了训练集没出现的情况就抓瞎。学习过程，就是在所有假设组成的空间中进行搜索的过程，搜索目标是找到与训练集匹配的假设。假设的表示一旦确定，假设空间及其规模大小就确定了。

有许多策略对假设空间进行搜索，比如自顶向下或自底向上，搜索过程不断删除与正例不一致的假设/与反例一致的假设。最后，就会获得与训练集一致的假设，这就是学得的结果。假设空间往往很大，但学习过程是基于有限的样本训练集进行的，所以会存在多个假设与训练集一致，称为版本空间(version space)。在不同的假设之间作选择，学习算法本身的归纳偏好(inductive bias)会起到关键作用，从而会选择这些假设中符合偏好的那个。

最常用的归纳偏好是“奥卡姆剃刀”原则，如无必要，勿增实体。但这也不是唯一的原则，而且很多时候也无法比较两种假设之间哪种更简洁。这时就要借助其他方法。甚至，有时候看上去A算法的泛化能力更强，但总存在一些问题，对于这些问题而言B算法的泛化能力却更强。因此，有必要限制算法的应用范围，不能拿规划午餐吃什么的算法来规划我们去餐厅的路径。

\begin{theorem}[没有免费的午餐]
    假设总体$X$是离散型随机变量，$H$是样本空间。令$P(h|\{x_i\},L_a)$代表算法$L_a$基于训练数据$\{x_i\}$产生假设$h$的概率，再令$f$代表我们希望学习的真实的映射。那么，$L_a$在训练集之外的所有样本上的误差为
    \begin{equation}
    Err_{ote}(L_a|\{x_i\},f)=\sum_{h}\sum_{x\in X-\{x_i\}}P(x)I_{\{x|h(x)\neq f(x)\}}(x)P(h|X,L_a)
    \end{equation}
    其中$I_{\{x|h(x)\neq f(x)\}}(x)$是示性函数。那么对于任意两个学习算法$L_a$和$L_b$，都有
    \begin{equation}
    \sum_{f}Err_{ote}(L_a|\{x_i\},f)=\sum_{f}Err_{ote}(L_b|\{x_i\},f)
    \end{equation}
\end{theorem}
\begin{proof}
    考虑二分类问题，真实目标函数可以是$f:X\to \{0,1\}$，配对一下共有$2^{|X|}$个。把所有可能的$f$按均匀分布对误差求和，有
    \begin{equation}
    \begin{aligned}
    \sum_{f}Err_{ote}(L_a|\{x_i\},f)&=\sum_{f}\sum_{h}\sum_{x\in X-\{x_i\}}P(x)I_{\{x|h(x)\neq f(x)\}}(x)P(h|\{x_i\},L_a)\\
    &=\sum_{x\in X-\{x_i\}}P(x)\sum_{h}P(h|\{x_i\},L_a)\sum_{f}I_{\{x|h(x)\neq f(x)\}}(x)
    \end{aligned}
    \end{equation}
    对于均匀分布而言，给定$h$以及$x$，有一半的$f$结果与$h$不一致，从而
    \begin{equation}
    \sum_{f}I_{\{x|h(x)\neq f(x)\}}(x)=\frac{1}{2}2^{|X|}=2^{|X|-1}
    \end{equation}
    另一方面，给定了样本外的观察值$x$，将基于此训练数据、此算法产生各种不同假设的条件概率加总起来，总和当然是1，也就是
    \begin{equation}
    \sum_{h}P(h|\{x_i\},L_a)=1
    \end{equation}
    因此算法在训练集之外的所有样本上的误差
    \begin{equation}
    \sum_{f}Err_{ote}(L_a|\{x_i\},f)=2^{|X|-1}\sum_{x\in X-\{x_i\}}P(x)
    \end{equation}
    是一个与算法$L_a$无关的量。\qed
\end{proof}
但是，我们真实面临的某种特殊问题中，$f$显然不是均匀分布。因此机器学习仍有意义，只是我们必须仔细考虑模型的适用范围。

\section{模型评估与选择}
\paragraph{经验误差}将分类错误的样本数占样本总数的比例称为错误率(error rate)，而正确率则称作精度(accuracy)。一般地，将学习器的实际预测输出与样本的真实输出之间的差异称为误差(error)。在训练集上的误差称为训练误差(training error)或经验误差(empirical error)；而在测试集上的误差称为泛化误差(generalizaiton error)。

一般来讲，不能事先知道测试集长什么样，因此只能努力减少经验误差。然而，如果经验误差太小，则可能陷入了过拟合(overfitting)的境地，把某些只属于训练集的特征当成了所有这类数据的特征，比如当训练集里的人都是白人时，一到测试集里，模型就不把黑人当人看了。但是，如果训练集里的性质没学好，则陷入了欠拟合(underfitting)的境地，看到哺乳动物都当人了。

欠拟合较好解决；但过拟合则非常麻烦，无法完全解决。在实验上，常常使用测试集来作为新样本，用测试的误差来作为泛化误差的近似。测试集应当尽可能与训练集互斥，不能考原题，否则算作弊，作不得数。

\paragraph{数据集处理}对于数据集$D$有限的场景，既要训练，又要测试，则需要从中作一定的处理，来产生训练集$S$和测试集$T$。一种办法是留出法，直接对数据集作分割，大头作训练集，小头作测试集。这种留出应该尽量遵循抽样的原则，比如分层抽样、等距抽样等。而且，评估结果的时候，还要多次随机抽样，每次产生一对测试集和训练集之后就算错误率，最后取平均。也有的做法是交叉验证，把数据划分为几份，交替取一份作测试，其余训练，最后算误差均值。

也有时候用自助法(bootstrapping)，其实就是有放回的采样。给定包含$m$个样本的数据集$D$，对其采样产生数据集$D'$：每次随机从$D$中挑选一个样本，将其拷贝放入$D'$，然后再将该样本放回初始数据集$D$中，使得该样本在下次采样时仍能采到。过程重复$m$次，就得到了$m$个样本的数据集$D'$，是为自助采样。

对于$m$次采样，每次有放回地采集一个样本，则某个样本始终未被采到的概率是
\begin{equation}
\left(1-\frac{1}{m}\right)^{m}\to \frac{1}{e},\quad m\to \infty
\end{equation}
因此，大约有$1/3$的样本是从未被采样的。我们将$D'$作训练集，将$D-D'$作测试集，在测试集中有$1/3$的数据是没有在训练集中出现过的。这种测试结果称为包外估计(out-of-bag estimate)。在数据集小、难以有效划分训练/测试集时很有用，但它会改变初始数据集的分布，引入估计偏差。所以在初始数据量足够时，留出法和交叉验证法更常用。

\paragraph{调参}大多数学习算法也有参数需要设定，也就是要调参，实际上是对模型作一个选择的过程。一般做法是对每个参数选定一个范围和变化步长。给定$m$个样本的数据集$D$，在模型评估和选择中由于需要留出一部分数据进行测试，因此我们只使用了一部分数据训练模型。因此在模型选择完成之后，学习算法和参数就固定了下来，这时应该用$D$重新训练模型，这样能包含全部样本，这样的模型才是最终交付的版本。

有时，学得模型在实际使用中遇到的数据称为测试数据，于是为了加以区分，在选择、评估模型时用的数据称为验证集(validation set)。

\paragraph{性能度量指标} 对学习器的泛化性能进行评估时，要用到性能度量(performance measure)指标。在预测任务中，给定样例集$D=\{(x_i,y_i)\}$，其中 $y_i$是$x_i$的真实标记。要评估学习器$f$的性能，就要把学习器预测结果$f(x)$与真实标记$y$进行比较。
\begin{definition}[均方误差]
    对于含有$m$个样本的离散样例集$D$，学习器$f$，称
    \begin{equation}
    Err(f;D)=\frac{1}{m}\sum_{i=1}^m (f(x_i)-y_i)^2
    \end{equation}
    为均方误差。对于连续样例，也就是数据分布$D$的概率密度$p$，称
    \begin{equation}
    Err(f;D)=\int_{\mathbb{R}}(f(x)-y)^2p(x)dx
    \end{equation}
    为均方误差。
\end{definition}
\begin{definition}[错误率和精度]
    对于含有$m$个样本的离散样例集$D$，学习器$f$，称
    \begin{equation}
    Err(f;D)=\frac{1}{m}\sum_{i=1}^m I_{\{f(x_i)\neq y_i\}}(i)
    \end{equation}
    为分类错误率；称
    \begin{equation}
    acc(f;D)=1-Err(f;D)
    \end{equation}
    为精度。类似地，对于连续情形，数据的概率密度为$p(x)$，称
    \begin{equation}
    Err(f;D)=\int_{\mathbb{R}}I_{\{f(x)\neq y\}}(x)p(x)dx
    \end{equation}
    为错误率，而称
    \begin{equation}
    acc(f;D)=1-Err(f;D)
    \end{equation}
    为精度。
\end{definition}
对于搜索推荐领域，也常用查全率和查准率作为性能度量标准。考虑二分类问题，根据其真实类别和学习器预测类别的组合，可以划分为
\begin{table}[h]
    \begin{tabular}{ccc}
        \hline
        真实情况&预测结果为正例&预测结果为反例\\
        \hline
        正例&真正例:True Positive(TP)&假反例:False Negative(FN)\\
        反例&假正例:False Positive(FP)&真反例:True Negative(TN)\\
        \hline
    \end{tabular}
\centering
\caption{分类结果混淆矩阵(confusion matrix)}
\end{table}
于是可以定义查准率和查全率
\begin{definition}[查准率和查全率]
    称
    \begin{equation}
    P=\frac{TP}{TP+FP}
    \end{equation}
    为查准率 (精确率)，表示预测结果为正时，真的正例占有的比；称
    \begin{equation}
    R=\frac{TP}{TP+FN}
    \end{equation}
    为查全率 (召回率)，表示真实情况为正时，预测结果为正占有的比。
\end{definition}
一般而言，查准率和查全率是矛盾的，当标准过于严格，查准率高，就会有很多正例被漏掉；当标准过于宽松，查全率高，宁可错杀一百不可放过一个，查准率就低了。

如果学习器$f_a$的查准率和查全率都比$f_b$高，那么$f_a$就肯定比$f_b$要更好。但很多情况下并不能这么比较。那么就可以比较学习器在查准率与查全率相等时，它们的取值，也就是平衡点(Break-Event Point)。另外，更常用的时查准率和查全率的调和平均
\begin{equation}
\frac{1}{F_1}=\frac{1}{2}\left(\frac{1}{P}+\frac{1}{R}\right)
\end{equation}
在不同的系统中，对查全率和查准率有不同的需求，因此常用加权调和平均：
\begin{equation}
\frac{1}{F_{\beta}}=\frac{1}{1+\beta^2}\left(\frac{1}{P}+\frac{\beta^2}{R}\right)
\end{equation}

有时，学习器会为测试样本给出一个概率预测，这时就可以根据预测结果，把样本进行排序。接着选取一个概率值进行截断，大于这个概率的取正例，小于的取反例。然后计算查准率和查重率，作为横纵坐标画成P-R曲线上的一个点；取各种概率值(从0到1)截断，就得到了许多点，这些点就组成了P-R曲线。

排序本身的质量好坏，也就体现了综合考虑学习器在一般情况下泛化性能的好坏。受试者工作特征曲线(Receiver Operating Characteristic, ROC)可描述这种泛化性能，根据学习器的预测结果进行排序，按照顺序逐个把样本作为正例进行预测，每次计算出真正例率(True Positive Rate, TPR)和假正例率(False Positive Rate)的值，分别以它们为横、纵坐标作图，就得到了ROC曲线。其中，
\begin{equation}
TPR= \frac{TP}{TP+FN},\quad FPR=\frac{FP}{TN+FP}
\end{equation}
然后，比较ROC曲线下的面积，也就是AUC(Area Under ROC Curve)，就可以判定学习器的好坏。
\begin{table}[h]
    \begin{tabular}{cccc}
        \hline
        TPR&FPR&混淆矩阵值&意义\\
        \hline
        0&0&TP=FP=0&无用，分类器把所有样本都划为反例\\
        1&0&FN=FP=0&完美，分类器把所有样本都正确划分\\
        0&1&TP=TN=0&糟糕，分类器把所有样本都错误划分\\
        1&1&FP=FN=0&无用，分类器把所有样本都划为正例\\
        \hline
        
    \end{tabular}
\centering
\caption{ROC曲线各个点的意义}
\end{table}

由此可以看出，ROC曲线越向左上角靠拢，分类器越好。当AUC=1时，这就是个完美的分类器；而当AUC=0.5时，这个分类器和随即猜测没什么两样，没有预测价值。

\begin{definition}[损失]
    给定$m^+$个正例，$m^-$个反例，令$D^+$和$D^-$分别表示正、反例集合，则排序损失定义为
    \begin{equation}
    l_{rank}=\frac{1}{m^+ m^-}\sum_{x^+\in D^+}\sum_{x^-\in D^-}\left(I_{\{x|f(x^+)<f(x^-)\}}(x)+\frac{1}{2}I_{\{x|f(x^+)=f(x^-)\}}(x)\right)
    \end{equation}
\end{definition}
这串公式的意思是，对于每个正例预测值比反例还小的情形，记一个罚分，如果相等，记半个罚分。AUC$=1-l_{rank}$。

有时，不同类型的错误所造成的后果不同，因而为了权衡不同类型错误所造成的不同损失，可以为错误赋予“非均等代价(unequal cost)”。以二分类任务为例，我们可以根据环境设置一个代价矩阵。如果把第一类的东西判作第二类非常危险，则$cost_{12}$较大，而把第二类的东西判成第一类的相对安全，则$cost_{21}$较小。正确识别就没有危险性，因此$cost_{11}=cost_{22}=0$。

在上面的损失中，我们其实隐含了每个错误都是相同代价的假设，因为每种错误的罚分都是一样大的。而如果添加上代价，也就是在罚分的时候加权，就得到了代价敏感错误率

\begin{definition}[代价敏感错误率]
    给定$m$个样本，令$D^+$和$D^-$分别表示正、反例集合，则代价敏感错误率定义为
    \begin{equation}
    Err(f;D;cost)=\frac{1}{m}\left(\sum_{x\in D^+}I_{\{x|f(x)\neq y\}}(x)\times cost_{12}+\sum_{x\in D^-}I_{\{x|f(x)\neq y\}}(x)\times cost_{21}\right)
    \end{equation}
\end{definition}

相应地，ROC曲线也就被代价曲线所取代，以描述学习器的期望总体代价。代价曲线的横轴是取值为$[0,1]$的正例概率代价
\begin{equation}
P(+)cost=\frac{p\times cost_{12}}{p\times cost_{12}+(1-p)\times cost_21}
\end{equation}
而纵轴是取值为$[0,1]$的归一化代价
\begin{equation}
cost_{norm}=\frac{(1-FPR)\times p\times cost_{12}+FPR\times (1-p)\times cost_{21}}{p\times cost_{12}+(1-p)\times cost_21}
\end{equation}
其中，$p$是样例为正例的概率。绘制代价曲线的方法是，对于每个ROC曲线上的点，都在代价曲线平面上找到$(0,FPR)$和$(1,1-FPR)$两点，连成线段。这些线段包络起来，下面的部分就是学习器的期望总体代价。

\paragraph{比较检验}
依照实验评估方法(比如留出法、交叉验证法、自助法等)，计算性能度量指标(比如均方误差、错误率、查准率、损失、代价敏感错误率)，画出ROC曲线或代价曲线，似乎就能比较学习器的性能了。然而，我们实际上需要比较的是泛化性能，而不是测试性能；另外学习算法以及测试集本身都具有一定的随机性。因此，我们需要引入假设检验。

在假设检验中，根据假设检验一章中介绍的流程，首先要有原假设$H_0$以及备择假设$H_1$：
\begin{equation}
H_0:\epsilon\leq\epsilon_0,\quad H_1:\epsilon>\epsilon_0
\end{equation}
在这里，我们使用泛化错误率$\epsilon$作为待检验的参数，而使用测试错误率$\hat{\epsilon}$作为统计量。$\epsilon_0$是一个常数，我们想看看错误率是否小于$\epsilon_0$。

显然，在二分类问题中，模型输出的总体服从两点分布$X\sim B(1,\epsilon)$，我们根据模型输出的观察值$x_i$来判定，在$1-\alpha$的把握下，原命题是正确的，需要保留。

对于两点分布总体，测试样本容量为$m$，采用检验统计量$\bar{X}\sim B(m,\epsilon)$。当$\epsilon=\epsilon_0$时，我们最有可能犯下第一类错误，也就是在$H_0$为真的情况下拒绝了它。此时有
\begin{equation}
\sum_{i=c}^{m} \begin{pmatrix}
m\\\epsilon_0
\end{pmatrix}\epsilon_0^{i}(1-\epsilon_0)^{m-i}\leq\alpha
\end{equation}
其中$c$是临界值。如果在测试中，发现检验统计量$\bar{X}\leq c$，也就是错误分类的数量小于$c$，那么就说明我们有$1-\alpha$的把握(以$1-\alpha$的置信度认为)保留原假设$H_0$；否则如果发现$\bar{X}\geq c$，那么就说明我们有$\alpha$的把握(以$\alpha$的置信度)拒绝原命题$H_0$。

在很多时候，并非仅做一次留出法进行估计，而是做很多次留出法，这样会得到多个测试错误率作为统计量$\epsilon_1,\cdots,\epsilon_n$，依照中心极限定理，在大样本情形它们服从正态分布$\epsilon\sim N(\mu,\sigma^2)$。在方差$\sigma^2$未知的情形，我们用样本方差$S^2$代替$\sigma^2$。用
\begin{equation}
\tau=\frac{\bar{\epsilon_i}-\epsilon_0}{S/\sqrt{n}}\sim t(n-1),\quad \bar{\epsilon_i}=\frac{1}{n}\sum_{i=1}^n \epsilon_i
\end{equation}
作为检验统计量，其服从自由度为$n-1$的$t$分布。

对于两个学习器$A$和$B$，使用$k$折交叉验证法得到的测试错误率分别为$\epsilon_1^A,\cdots,\epsilon_k^A$和$\epsilon_1^B,\cdots,\epsilon_k^B$，其中$\epsilon_i^A$和$\epsilon_i^B$是在第$i$折上训练集/测试集上得到的结果。这时就可以用$k$折交叉验证“成对$t$检验”来进行比较检验。如果两个学习器的性能相同，那么它们使用相同的训练、测试集得到的测试错误率应当相同，也就是$\epsilon_i^A=\epsilon_i^B$。

在$k$折交叉验证中，我们选取的原假设及备择假设是
\begin{equation}
H_0:\Delta=0,\quad H_1:\Delta\neq 0
\end{equation}

我们选取统计量
\begin{equation}
\bar{\Delta}=\frac{1}{k}\sum_{i=1}^k (\epsilon_i^A-\epsilon_i^B)
\end{equation}
$\epsilon$服从正态分布，用样本方差$S^2$代替方差$\sigma^2$，检验统计量
\begin{equation}
\tau=\frac{\bar{\Delta}}{S/\sqrt{k}}\sim t(k-1)
\end{equation}
从而如果$\tau$的观察值出现在了以0为中心，$1-\alpha$的面积之下，就保留原假设，认为$A$和$B$的错误率相同；否则就拒绝原假设。

除此之外，要比较二分类问题下算法$A$和$B$的优劣性，还可以用McNemar检验；如果要比较多个算法，则可以使用Friedman检验。在Friedman检验中，如果原假设$H_0:$“所有算法都相同”被拒绝，那么就用后续检验(post-hoc test)来进一步区分各算法，常用的有Nemenyi后续检验。

\paragraph{偏差与方差}
考虑测试样本$x$，$y_D$为数据集中的标记，$y$为$x$的真实标记，$f(x;D)$为训练集$D$上学得模型$f$在$x$上的预测输出。则学习算法的期望预测是
\begin{equation}
\bar{f}(x)=E_Df(x;D)
\end{equation}
其中$E_D$表示在各种数据集中，取期望。使用样本数相同的不同训练集产生的方差是
\begin{equation}
Varx=E_D(f(x;D)-\bar{f}(x))^2
\end{equation}

噪声是
\begin{equation}
\epsilon^2=E_D(y_D-y)^2
\end{equation}
期望输出和真实标记的差别称为偏差(bias)，也就是
\begin{equation}
bias^2(x)=(\bar{f}(x)-y)^2
\end{equation}
为了便于讨论，假定噪声期望为零，也就是$E-D(y_D-y)=0$。由此，对于在测试集上的误差，也就是泛化误差，我们有平方和分解式：
\begin{equation}
\begin{aligned}
Err(f;D)&=E_D(f(x;D)-y_D)^2=E_D(f(x;D)-\bar{f}(x))^2+E_D(\bar{f}(x)-y)^2+E_D(y-y_D)^2\\
&=Varx+bias^2(x)+\epsilon^2
\end{aligned}
\end{equation}
这表明，泛化误差可分解为偏差、方差与噪声之和。

\begin{enumerate}
    \item 偏差$bias^2(x)$表示学习算法的期望预测与真实结果的偏离程度，是学习算法本身的拟合能力，代表了训练程度。
    \item 方差$Varx$度量了训练集的变化导致的学习性能的变化
    \item 而噪声$\epsilon^2$则是学习任务本身的性质，在这个任务上，总体具有一定的方差，从而导致训练集的不稳定，因而任何学习算法在这里都会出现这部分泛化误差。这是学习算法所能达到的泛化误差的下界。
\end{enumerate}

一般来说，偏差和方差是有冲突的。训练不足，偏差主导了泛化错误率，而因为学习率较低，所以训练数据的扰动不足以导致学习器产生显著变化，所以方差不重要；训练过度，偏差逐渐消除了，但学习率太高，任何一点训练数据的扰动都会影响到学习器，所以偏差主导了泛化误差，发生过拟合。

\section{构造目标函数}

在机器学习的过程中，我们预先定义一个模型，它具有参数。我们所作的，便是根据样本，对参数进行点估计。回顾统计学中的方法：点估计、区间估计、贝叶斯估计。其不同之处在于，点估计所得的结果是参数的值，区间估计所得的是参数置信区间，而贝叶斯估计则给出的是参数的后验分布。在实际应用中，我们希望得到的是一个准确的模型，因此我们使用点估计的办法。在点估计中，则有如下方法：
\begin{enumerate}
    \item 矩法估计。这种办法只扫描一遍各个样本，给出各个样本矩，然后根据样本矩反解出参数。这种做法对于简单的模型适用，但对于复杂的机器学习模型来说就不是很实用了。如果样本数量较少，那么它大概率无法学到有效特征；如果样本数量过多，反解样本数目维度的方程组是巨大的计算性能开销——它会远高于优化、迭代的方法。
    \item 极大似然估计。给定模型之后，只要再给定参数，分布就确定了。于是乎，出现某个样本的概率也就确定了，数据集呈现出当前形态的概率也就确定了 (为各个独立样本的概率的乘积)。我们逐一测试各个可能的参数，找到使得数据集呈现出当前形态的概率达到最大的那组参数，便是极大似然估计。当然，实际使用中既然似然函数形式确定，以参数为自变量，那么我们当然以一般的函数分析的办法来求参数，而不是逐个参数去尝试。
    \item 均方误差最小估计。试图找到这样的参数值，使得模型的预测与真实之间的均方误差最小。我们在线性拟合一章中就使用均方误差最小估计来导出最小二乘法。
    \item 贝叶斯估计。贝叶斯估计的流程在对应章节中有详细介绍。它先给出模型，以及先验分布，即可得到样本和参数的联合分布。然后，根据贝叶斯公式，即可得到参数在当前样本下的条件分布，也就是后验分布。需要注意的是，贝叶斯估计和其他估计不同，它给出的是参数的分布，而不仅仅是参数值。
    \item 最大后验估计。贝叶斯估计中会给出参数的后验分布，但我们显然也可以采用参数最有可能出现的那个值，作为我们的点估计。最大后验估计的好处是，不需要经过贝叶斯估计所需要的可怕计算过程。
\end{enumerate}
以上只是一些最常用的方法。还有一些，例如正则化方法 (岭回归、Lasso 等)、准则估计、插值估计、经验贝叶斯估计等。接下来，我们将使用线性模型，来一一使用这些方法进行参数点估计。

线性模型的基本形式是，给定$d$个属性描述的示例$\vec{x}=(x^1,\cdots,x^d)^T$，通过属性的线性组合来进行预测的函数
\begin{equation}
f(x)=\sum_{i=1}^{d}w^ix^i=\vec{w}^{T}\vec{x}
\end{equation}
在这里，为了方便，我们省略了偏置项$b$。给定数据集$D=\{(\vec{x}_1,y_1),\cdots,(\vec{x}_m,y_m)\}$，其中$\vec{x}_i=(x_i^1,\cdots,x_i^d)^T,\ i=1,\cdots,m$。

\paragraph{均方误差最小估计 (MSE)} 在线性回归任务中，我们希望找到$(\hat{\vec{w}})$，使得
\begin{equation}
\sum_{i=1}^{m}(f(x_i)-y_i)^2=\sum_{i=1}^{m}(y_i-\sum_{j=1}^{d}w_i^jx_i^j)^2
\end{equation}
达到最小。所采用的方法就是所谓的最小二乘法，在线性回归一章中已经详细叙述。

\paragraph{矩法估计} 在估计一般随机变量的参数时，矩法估计比较简单方便。但涉及到了复杂的模型时，矩法估计就不那么方便，而且效果也不太好了。所以矩法估计方法很少被用来作为机器学习及深度学习的目标函数。

如果一定要用矩法估计，由于我们的线性模型没有偏置项，所以直接考虑二阶矩，需要找到参数 $\vec{w}^T$，满足
\begin{equation}
    Cov(y,\vec{x}) = Cov(\vec{w}^T\vec{x}, \vec{x})
\end{equation}
此时，等式右边 
\begin{equation}
    \begin{aligned}
    Cov(\vec{w}^T\vec{x}, \vec{x}) =& E\rbk{(\vec{x} - E\vec{x})(\vec{w}^T\vec{x} - E(\vec{w}^T\vec{x}))}\\
    =& E\rbk{\vec{x}\vec{w}^T\vec{x} - E(\vec{x})\vec{w}^T\vec{x} - \vec{x}E(\vec{w}^T\vec{x}) + E\vec{x}E(\vec{w}^T\vec{x})}\\
    =& E\rbk{\vec{x}\vec{w}^T\vec{x}} - E(\vec{x})E(\vec{w}^T\vec{x})\\
    =& E\rbk{\vec{x}\vec{w}^T\vec{x}} - E(\vec{x})\vec{w}^TE(\vec{x})
    \end{aligned}
\end{equation}
而等式左边：
\begin{equation}
    \begin{aligned}
    Cov(y,\vec{x}) =& E\rbk{(\vec{x} - E\vec{x})(y - Ey)}\\
                    =& E\rbk{\vec{x}y} - E\vec{x}Ey
    \end{aligned}
\end{equation}
要让等式成立，需要 
\begin{equation}
    E\rbk{\vec{x}\vec{w}^T\vec{x}} - E(\vec{x})\vec{w}^TE(\vec{x}) = E\rbk{\vec{x}y} - E\vec{x}Ey
\end{equation}
注意到，根据我们的模型，$Ey = w^TEx$ 天然成立，所以等式成立要求 $\vec{w}$ 满足 
\begin{equation}
    E(\vec{x}\vec{w}^T\vec{x}) = E(\vec{x}y)
\end{equation}
对于任意的采样点 $\vec{x}_i, y_i$，都应当满足上面这个等式。所以 
\begin{equation}
    \sum_{i=1}^{m}\vec{x}\vec{x}^T\vec{w} = \sum_{i=1}^{m}\vec{x}_i y_i
\end{equation}
上面这个方程正是正规方程。不意外地，最终我们通过矩法估计所得的参数估计$\hat{w}$结果，和 MSE 的结果是一致的。不过，我们这里直接给出了一个线性方程组，而没有以目标函数的形式进行优化计算。不一方面任何线性方程组都可以使用优化方法求解，另一方面我们的线性方程组与优化方法给出来的解是等价的，所以也就无需在意这些。尤其是，矩法估计在模型参数求解上很少用到，我们在这进行推导只是为了表明，各种之前介绍过的参数点估计的方法，都是相当于用来构造目标函数的。

\paragraph{极大似然估计 (MLE)} 换一种角度来看，我们之前选择的目标误差函数是MSE，也就是平均平方和达到最小。现在，我们换一个目标误差函数。我们希望找到$\hat{w}$，使得概率
\begin{equation}
P(y_1,\cdots,y_m|\hat{w},x_1,\cdots,x_m)=\prod_{i=1}^{m}P(y_i|\hat{w}, x_i)
\end{equation}
达到最大。这正是我们在极大似然估计里所作的，唯一的不同就是在极大似然估计中，我们当时是对一般的分布进行估计，而现在我们需要对条件分布进行估计，所谓的条件就是数据集的输入$x_i$。对似然函数取对数，注意$y_i$假设是由一个线性函数以及一个正态随机变量组合而成的：
\begin{equation}
    P(y_i|\hat{w},x_i) \sim N(\hat{w}^Tx_i, \sigma^2)
\end{equation}
因此实际上就是要
\begin{equation}
\ln\left(\prod_{i=1}^{m}P(y_i|\hat{w},x_i)\right)=-\frac{m}{2}\ln(2\pi\sigma^2)-\sum_{i=1}^{m}\frac{\|\hat{y}_i-y_i\|^2}{2\sigma^2}
\end{equation}
达到最大值。前面一项是常数，而后一项达到最大值，正与MSE达到最小值是等价的。换言之，在线性模型中，我们采用不同的方法，得到了相同的目标误差函数，从而可以使用同样的算法来计算$\hat{w}$。

\paragraph{贝叶斯估计} 另一方面，我们也可以用贝叶斯估计的方法，来重新审视线性模型。在贝叶斯估计一章中，我们知道，需要根据参数 $\theta$ 的先验信息，确定其先验分布 $\pi(\theta)$。在线性模型中，就相当于确定先验分布 $\pi(w)$。于是，样本和参数的联合分布密度为 
\begin{equation}
    h(y_i, x_i, w, b) = f(y_i|x_i, w)\pi(w)
\end{equation}
一般而言，我们假设先验是一个正态分布：
\begin{equation}
    \pi(w) = N(w;\mu,\Lambda)
\end{equation}
其中 $\mu$ 是 $w$ 的正态分布均值，而 $\Lambda$ 是多元正态分布的协方差矩阵。一般可以假定 $w^j$是独立的，所以协方差矩阵是对角矩阵。而根据线性模型的一般假定，在给定参数和输入值的条件下，样本的分布为 
\begin{equation}
    f(y_i|x_i, w) = N(y_i; w^Tx_i, 1)
\end{equation}
其中，我们根据标准的 MSE 公式，假设 $y$ 上的方差为 1。在这里方差是多少并不影响结果。根据贝叶斯推断的手续，我们接下来就要计算联合密度：
\begin{equation}
    h(y_i, x_i, w) \propto \exp\rbk{-\frac{1}{2}\sum_{i=1}^{m}(y_i - w^Tx_i)^2 - \frac{1}{2}(w-\mu)^T\Lambda^{-1}(w-\mu)}
\end{equation}
其中，$\Lambda^{-1}$是协方差矩阵 $\Lambda$ 的逆矩阵。这个协方差矩阵一般是正定的对角阵，所以其逆矩阵就是所有对角元取倒数。

求得了联合密度之后，就可以求出参数分布了：
\begin{equation}
    \pi(w|y_i,x_i) = \frac{h(y_i, x_i, w)}{\int_{w}f(y_i|x_i, w)\pi(w)\dd{w}}
\end{equation}
注意，这里的输入值$x$的分布是均匀的，所以不参与计算中。在分母中，对 $w$ 积分，意味着其分布与 $w$ 相互独立。考虑到，$w$ 的分布，作为正态分布，总是需要归一化的，并且我们最终会对 $w$ 的后验分布中，达到最大密度的那个值 (最大后验估计) 感兴趣，因而分母并不重要，只需要关注分子即可。

舍去分母，对分子展开后可写为
\begin{equation}
    \begin{aligned}
    \pi(w|y_i, x_i) \propto& \exp\rbk{-\frac{1}{2}\sum_{i=1}^{m}(y_i^2 - 2y_iw^Tx_i + (w^Tx_i)^2)}\cdot \\&\cdot\exp\rbk{-\frac{1}{2}\rbk{w^T\Lambda^{-1}w - \mu^T\Lambda^{-1}w - w^T\Lambda^{-1}\mu + \mu^T\Lambda^{-1}\mu}}
    \end{aligned}
\end{equation}
和舍去分母同样的理由，分子中的 $y_i^2$ 和 $\mu^T\Lambda^{-1}\mu$ 都是会在归一化步骤中被抹去的项，所以我们忽略它们不管，因而 
\begin{equation}
    \pi(w|y_i, x_i) \propto \exp\rbk{-\frac{1}{2}\sum_{i=1}^{m}(-2y_iw^Tx_i + (w^Tx_i)^2) - \frac{1}{2}\rbk{w^T\Lambda^{-1}w - 2w^T\Lambda^{-1}\mu}}
\end{equation}
其中，注意到 $\Lambda$ 是对角正定阵，所以矩阵的乘法$w^T\Lambda^{-1}\mu$ 是可以换序的。

现在，定义
\begin{equation}
    \Lambda_m = \rbk{\sum_{i=1}^{m}x_ix_i^T + \Lambda^{-1}}^{-1},\quad \mu_m = \Lambda_m\rbk{\sum_{i=1}^{m}y_ix_i + \Lambda^{-1}\mu}
\end{equation}
从而 
\begin{equation}
    \Lambda^{-1} = \Lambda_m^{-1} - \sum_{i=1}^{m}x_ix_i^T,\quad \Lambda^{-1}\mu = \Lambda_m^{-1}\mu_m - \sum_{i=1}^{m}y_ix_i
\end{equation}
代入到后验分布中，可得 
\begin{equation}
    \begin{aligned}
    \pi(w|y_i,x_i)\propto &\exp\rbk{-\frac{1}{2}\sum_{i=1}^{m}(-2y_iw^Tx_i + (w^Tx_i)^2)}\cdot\\
    &\exp\rbk{ - \frac{1}{2}\rbk{w^T\Lambda_m^{-1}w - w^T\rbk{\sum_{i=1}^{m}x_ix_i^T}w - 2 w^T\rbk{\Lambda_m^{-1}\mu_m - \sum_{i=1}^{m}y_ix_i}}}
    \end{aligned}
\end{equation}
发现显式关于 $y_i$ 的项以及关于 $x_i$ 的项均可抵消。整理可得
\begin{equation}
    \pi(w|y_i,x_i) \propto \exp\rbk{ - \frac{1}{2}\rbk{w^T\Lambda_m^{-1}w - 2w^T\Lambda_m^{-1}\mu_m}}
\end{equation}
经过配方，并像之前那样舍弃与 $w$ 无关的因子，可得 
\begin{equation}
    \pi(w|y_i,x_i)\propto \exp\rbk{-\frac{1}{2}\rbk{(w^T-\mu_m)^T\Lambda_m^{-1}(w^T - \mu_m)}}
\end{equation}
这是一个多元正态分布。重要的是，其期望为 $\mu_m$，也正是取到最大后验估计的点。换句话说，$\mu_m$不是别的，正是我们想要的$w$的最大后验估计 $\hat{w}$。

现在，我们来回顾 $\mu_m$ 的形式，我们发现它和 $\Lambda^{-1}\mu $ 有关，而它们是先验决定的。如果我们对系数 $w$ 的把握非常弱，$\Lambda$ 的各项对角元都非常大，$\mu$趋于零，那么 
\begin{equation}
    \lim_{\|\Lambda\|\to\infty}\lim_{\|\mu\|\to 0} \mu_m = \rbk{\sum_{i=1}^{m}x_ix_i^T}^{-1}\rbk{\sum_{i=1}^{m}y_ix_i}
\end{equation}
这和最小二乘法所得的结果是一致的。这说明，当我们不加任何先验信息的时候，贝叶斯最大后验估计的结果，与 MSE、MLE 等方法一致。

当我们加了很强很强的先验呢？那 $\mu_m = \mu$，样本就几乎没有什么影响了，模型的参数将和我们所加的先验一致。这和贝叶斯估计的精神是一致的。

当我们加的先验不是很大，也不是很小，有趣的事情就发生了。设 $\Lambda = \frac{1}{\alpha}I$，其中 $I$ 是$d\times d$的单位矩阵。此时：
\begin{equation}
    \mu_m = \rbk{\sum_{i=1}^{m}x_ix_i^T + \alpha I}^{-1}\rbk{\sum_{i=1}^{m}y_i x_i + \alpha\mu}
\end{equation}
这个结果，和我们在 MSE 的目标函数中，添加 $\alpha w^Tw $ 的权重衰减惩罚所得的结果，是一致的。(该结果可以自行验算)

\paragraph{最大后验估计 (MAP)} 在贝叶斯估计中我们已经做过一次了，当时我们所得的参数 $w$ 的形式为正态分布，所以我们直接取了其均值 $\mu_m$ 作为最大后验估计。但贝叶斯估计的冗长流程令人畏惧，所幸如果我们只是进行点估计的话，不需要经过这么长的流程。

对于参数为 $w$ 的线性模型，其最大后验估计为 
\begin{equation}
    \hat{w} = \arg\max_{w} \pi(w|x_i,y_i) = \arg\max_{w} f(y_i|x_i,w)\pi(w) 
\end{equation}
考虑到，对 $\pi(w|x_i, y_i)$ 求取到最大值所对应的 $w$，和对其对数函数取到最大值所对应的 $w$ 无异。所以 
\begin{equation}
    \hat{w} = \arg\max_{w}\rbk{\log f(y_i|x_i, w) + \log\pi(w)}
\end{equation}
其中第一项正是 MLE 中，我们使用的似然函数。而第二项则代表先验信息。从第一项来看，我们就能直接知道，最大后验估计与极大似然估计之间的关系——它只是加了一点先验信息而已，这些先验信息加到了目标函数中。

在贝叶斯估计一章中，我们还介绍了所谓贝叶斯参数估计。在那里，我们是使用 $\pi(w|x_i,y_i)$ 的期望来进行估计的。在线性模型下，根据我们前面的贝叶斯估计的结果，不难发现这两者是等价的。但在其他模型中则有所不同，需要从头取得参数的后验分布，然后计算其期望。考虑到贝叶斯估计对于机器学习乃至深度学习所使用的复杂模型来说过于困难，所以我们一般不使用这种方法。

% \begin{equation}
%     % h(y_i, x_i, w) \propto \exp\rbk{-\frac{1}{2}\rbk{w-\mu'}}
%     \pi(w|y_i, x_i) \propto \exp\rbk{\frac{1}{2}\rbk{-2y_i^TXw + w^Tx_i^Tx_iw + w^T\Sigma^{-1}w - 2\mu^T\Sigma^{-1}w}}
% \end{equation}

% 我们也可以用sigmoid函数，把线性模型改造成用以分类：
% \begin{equation}
% y=\frac{1}{1+e^{-\sum_{j=1}^{d}w^{j}x^{j}-b}},\quad \ln\frac{y}{1-y}=\sum_{j=1}^{d}w^{j}x^{j}+b
% \end{equation}

% 再对线性模型改造一下，考虑核技巧(kernel trick)，把$x^{j}$替换成核函数$k(x,x_i)$，从而用
% \begin{equation}
% f(x)=b+\sum_{i=1}^{m}\alpha_i k(x,x_i)=b+\sum_{i=1}^{m}\alpha_i \sum_{j=1}^{d}\phi^j(x)\phi^j(x_i)
% \end{equation}
% 来进行预测。我们用$\phi(x)$来处理非线性部分，剩下其他的参数就都是线性的了。采用这种策略的方法，就叫支持向量机(Support Vector Machine)。有时，$\phi(x)$很难算，但核函数$k(x,x_i)$却很容易计算。现代深度学习的复兴，就起源于神经网络能够在MNIST基准数据上，胜过RBF核的支持向量机。

\section{优化方法}
在选定了目标函数之后，我们就需要找到这样的参数值 $\vec{w}$，使得目标函数达到最小值 (或者最大值)。 
\begin{equation}
    \hat{w} = \arg\min_{w} J(\vec{w})
\end{equation}
其中 $J(\vec{w})$ 是目标函数。这显然是一个优化问题，其求解难度与目标函数有关，而目标函数又和模型的结构、构造优化函数的方法有关。如果目标函数是凸的，那么我们直接用凸优化方法，比如梯度下降法，便可以按指数精度来逼近最终的解。此外，如果目标函数非常简单，我们甚至可以通过求导数，并令导数等于零的方式得到 $\vec{w}$ 的解，这便是线性模型的情况。然而，很遗憾，大部分模型的复杂程度让我们无法使用这种简单的方法得到参数的点估计。

尽管，对非凸优化问题，贸然上梯度下降法是鲁莽的。但实验表明，这个方法还挺好用的。
\begin{definition}[梯度下降法]
    设 $\theta$是模型的参数，目标函数 $J(\theta)$ 为似然函数，那么梯度下降需要计算 
    \begin{equation}
        \hat{\vec{g}}_k = \frac{1}{n}\nabla_{\theta} \sum_{i=1}^{n}L(f(\vec{x}_i;\theta_k),\vec{y}_i)
    \end{equation}
    其中 $L(f(\vec{x}_i;\theta),\vec{y})$ 为样本 $\vec{x}_i,\vec{y}_i$ 的似然函数，$n$为训练集样本总数。从而将第 $k$ 步的参数 $\theta_k$ 参新为 
    \begin{equation}
        \theta_{k+1} = \theta_{k} - \epsilon \vec{g}
    \end{equation}
    其中 $\epsilon$ 是学习率。称这种优化方法为梯度下降法。
\end{definition}

当我们每次从样本中进行随机抽样，取出一部分计算梯度时，则这种优化方法就称为随机梯度下降：
\begin{definition}[随机梯度下降 (Stochastic Gradient Descent, SGD) 法]
    设 $\theta$是模型的参数，目标函数 $J(\theta)$ 可以分解为各个样本目标函数之和。我们从训练集中抽取包含 $m$ 个样本的小批量，其中 $\vec{x}_i$ 对应于目标 $\vec{y}_i$，那么第 $k$ 步的随机梯度下降需要计算 
    \begin{equation}
        \hat{\vec{g}}_k = \frac{1}{m}\nabla_\theta \sum_{i=1}^{m}L(f(\vec{x}_i;\theta_k),\vec{y}_i)
    \end{equation}
    其中 $L(f(\vec{x}_i;\theta),\vec{y})$ 为样本 $\vec{x}_i,\vec{y}_i$ 的似然函数。从而将第 $k$ 步的参数 $\theta_k$ 参新为 
    \begin{equation}
        \theta_{k+1} = \theta_k - \epsilon_k \hat{\vec{g}}_k
    \end{equation}
    其中 $\epsilon_k$ 是第 $k$ 步的学习率。我们称这种方法为随机梯度下降法。
\end{definition}
这里需要注意到，学习率是会变动的，从而与批量梯度下降不同。这是因为，在 SGD 中即使已经达到了目标函数最小值，由于小批量数据采样导致的噪声是不会消失的。
\begin{theorem}
    保证随机梯度下降收敛的充分条件为：
    \begin{equation}
        \sum_{k=1}^{\infty}\epsilon_k = \infty,\quad \sum_{k=1}^{\infty}\epsilon_k^2 < \infty 
    \end{equation}
\end{theorem}

在实践中，一般会选择线性衰减的学习率 
\begin{equation}
    \epsilon_k = (1-\alpha)\epsilon_0 + \alpha\epsilon_r,\quad \alpha = k/\tau 
\end{equation}
在第 $\tau$ 步迭代后，就使得 $\epsilon$ 保持常数 $\epsilon_r$。
此外，还有一些其他的衰减学习率的方法，比如余弦衰减、指数衰减等。

\begin{definition}[带动量的随机梯度下降法]
    设 $\theta$是模型的参数，目标函数 $J(\theta)$ 可以分解为各个样本目标函数之和。我们从训练集中抽取包含 $m$ 个样本的小批量，其中 $\vec{x}_i$ 对应于目标 $\vec{y}_i$，那么第 $k$ 步的随机梯度下降需要计算 
    \begin{equation}
        \hat{\vec{g}}_k = \alpha\hat{\vec{g}}_{k-1} + \frac{1}{m}\nabla_\theta \sum_{i=1}^{m}L(f(\vec{x}_i;\theta_k),\vec{y}_i)
    \end{equation}
    其中 $L(f(\vec{x}_i;\theta),\vec{y})$ 为样本 $\vec{x}_i,\vec{y}_i$ 的似然函数。从而将第 $k$ 步的参数 $\theta_k$ 参新为 
    \begin{equation}
        \theta_{k+1} = \theta_k - \epsilon_k \hat{\vec{g}}_k
    \end{equation}
    其中 $\epsilon_k$ 是第 $k$ 步的学习率。我们称这种方法为带动量的随机梯度下降法。
\end{definition}
带动量的随机梯度下降主要目的是解决 Hessian 矩阵的病态条件，以及随机梯度的方差。它对高曲率、小但一致、带有噪声的梯度有较好的效果。动量算法积累了之前梯度指数级衰减的移动平均，并且继续沿着该方向移动。如果动量算法观察到，梯度总是一致的 $\vec{g}$，那么它每次更新的值就会往 $-\vec{g}$ 的方向不断加速，直到更新步长大小为 $\epsilon|\vec{g}|/(1-\alpha)$。当 $\alpha = 0.9$ 时，就意味着最终带动量的随机梯度下降更新速度会达到一般随机梯度下降的 10 倍。

\begin{definition}[Nesterov 动量的随机梯度下降法]
    设 $\theta$是模型的参数，目标函数 $J(\theta)$ 可以分解为各个样本目标函数之和。我们从训练集中抽取包含 $m$ 个样本的小批量，其中 $\vec{x}_i$ 对应于目标 $\vec{y}_i$，那么第 $k$ 步的随机梯度下降需要计算 
    \begin{equation}
        \hat{\vec{g}}_k = \alpha\hat{\vec{g}}_{k-1} + \frac{1}{m}\nabla_\theta \sum_{i=1}^{m}L(f(\vec{x}_i;\theta_k + \alpha\hat{\vec{g}}_{k-1}),\vec{y}_i)
    \end{equation}
    其中 $L(f(\vec{x}_i;\theta),\vec{y})$ 为样本 $\vec{x}_i,\vec{y}_i$ 的似然函数。从而将第 $k$ 步的参数 $\theta_k$ 参新为 
    \begin{equation}
        \theta_{k+1} = \theta_k - \epsilon_k \hat{\vec{g}}_k
    \end{equation}
    其中 $\epsilon_k$ 是第 $k$ 步的学习率。我们称这种方法为带 Nesterov 动量的随机梯度下降法。
\end{definition}
带 Nesterov 动量的随机梯度下降法的关键在于，其在计算似然函数的时候，用的不是当前的参数 $\theta_k$，而是添加了一个修正项 $\tilde{\theta}_k = \theta_k + \alpha\hat{\vec{g}}_{k-1}$。在凸批量梯度的情况下，它将额外误差收敛率从 $O(1/k)$ 加速到 $O(1/k^2)$。然而，在 SGD 中，它却没有加速。

除了以上优化方法外，还有一些自适应的学习方法。显然，学习率是难以设置的超参数，而它对训练性能的表现极为关键。带动量的SGD引入了一些尝试，但这又引入了另一个超参数。我们自然要问，有没有其他方法。由此，引入了一些自适应的学习方法。

\begin{definition}[自适应梯度下降法 (Adaptative Gradient, AdaGrad)]
    设 $\theta\in\mathbb{R}^s$是模型的参数，目标函数 $J(\theta)$ 可以分解为各个样本目标函数之和。我们从训练集中抽取包含 $m$ 个样本的小批量，其中 $\vec{x}_i$ 对应于目标 $\vec{y}_i$，那么第 $k$ 步的随机梯度下降需要计算 
    \begin{equation}
        \hat{\vec{g}}_k = \frac{1}{m}\nabla_\theta \sum_{i=1}^{m}L(f(\vec{x}_i;\theta_k),\vec{y}_i)
    \end{equation}
    其中 $L(f(\vec{x}_i;\theta),\vec{y})$ 为样本 $\vec{x}_i,\vec{y}_i$ 的似然函数。设 $\vec{r}_k$ 为第 $k$ 步的梯度累积变量，逐元素应用更新 
    \begin{equation}
        r_{k+1}^{j} = r_k^j + (g_k^j)^2,\quad \forall j=1,\cdots,s
    \end{equation}
    从而将第 $k$ 步的参数 $\theta_k$ 参数更新为 
    \begin{equation}
        \theta_{k+1}^j = \theta_{k}^j - \frac{\epsilon}{\delta + \sqrt{r_{k+1}^j}}g_k^j,\quad \forall j = 1, \cdots, s 
    \end{equation}
    其中 $\epsilon$ 是全局学习率，$\delta$ 一般为小常数 $\sim 10^{-7}$，为了除法的数值稳定性而添加。
\end{definition}
AdaGrad 法可以在各个分量上独立适应所有模型参数的学习率，缩放每个参数反比于其所有梯度历史平方值总和的平方根。这样，具有损失最大偏导的参数相应地具有一个快速下降的学习率。在凸优化背景下，这种方法具有令人满意的理论性质，但在非凸优化的场景下， 从训练开始就累积梯度平方，会导致有效学习率过早、过快地减少。

\begin{definition}[均方根传播法 (Root Mean Square Propagation, RMSProp)]
    设 $\theta\in\mathbb{R}^s$是模型的参数，目标函数 $J(\theta)$ 可以分解为各个样本目标函数之和。我们从训练集中抽取包含 $m$ 个样本的小批量，其中 $\vec{x}_i$ 对应于目标 $\vec{y}_i$，那么第 $k$ 步的随机梯度下降需要计算 
    \begin{equation}
        \hat{\vec{g}}_k = \frac{1}{m}\nabla_\theta \sum_{i=1}^{m}L(f(\vec{x}_i;\theta_k),\vec{y}_i)
    \end{equation}
    其中 $L(f(\vec{x}_i;\theta),\vec{y})$ 为样本 $\vec{x}_i,\vec{y}_i$ 的似然函数。设 $\vec{r}_k$ 为第 $k$ 步的梯度累积变量，逐元素应用更新 
    \begin{equation}
        r_{k+1}^{j} = \rho r_k^j + (1-\rho) (g_k^j)^2
    \end{equation}
    其中 $\rho$ 是衰减速率超参数。计算参数更新 
    \begin{equation}
        \theta_{k+1}^j = \theta_{k}^j - \frac{\epsilon}{\delta + \sqrt{r_{k+1}^j}}g_k^j,\quad \forall j = 1, \cdots, s 
    \end{equation}
    其中 $\epsilon$ 是全局学习率，$\delta$ 一般为小常数 $\sim 10^{-6}$，为了除法的数值稳定性而添加。
\end{definition}
RMSProp 使用指数衰减 $\vec{r}$ 各分量的遥远历史，因而它避免了 AdaGrad 算法中有效学习率过早减小的问题。实验证明，RMSProp 是一种有效的非凸优化算法，广泛应用于深度学习中。除此之外，也可以将 RMSProp 与 Nesterov 动量形式结合。

\begin{definition}[自适应矩算法 (Adaptive Moments, Adam)]
    设 $\theta\in\mathbb{R}^l$是模型的参数，目标函数 $J(\theta)$ 可以分解为各个样本目标函数之和。我们从训练集中抽取包含 $m$ 个样本的小批量，其中 $\vec{x}_i$ 对应于目标 $\vec{y}_i$，那么第 $k$ 步的随机梯度下降需要计算 
    \begin{equation}
        \hat{\vec{g}}_k = \frac{1}{m}\nabla_\theta \sum_{i=1}^{m}L(f(\vec{x}_i;\theta_k),\vec{y}_i)
    \end{equation}
    
    设第 $k$ 步的有偏一阶矩估计为 $\vec{s}_k$，其更新为 
    \begin{equation}
        s_{k+1}^j = \rho_1 s_k^j + (1-\rho_1) g_k^j,\quad \forall j=1,\cdots,l
    \end{equation}
    其中 $\rho_1\in [0,1)$ 为有偏一阶矩估计的衰减速率超参数，一般设为 $0.9$。
    
    设第 $k$ 步的有偏二阶矩估计为 $\vec{r}_k$，其更新为 
    \begin{equation}
        r_{k+1}^j = \rho_2 r_k^j + (1-\rho_2) (g_k^j)^2,\quad \forall j=1,\cdots,l
    \end{equation}
    其中 $\rho_2\in [0,1)$ 为有偏二阶矩估计的指数衰减速率超参数，一般设为 $0.99$。

    利用 $\vec{s}$, $\vec{r}$ 以及 $\hat{\vec{g}}$ 对参数进行更新：
    \begin{equation}
        \theta_{k+1}^j = \theta_{k}^j - \epsilon\dfrac{\frac{s_{k+1}^j}{1-\rho_1^k}}{\sqrt{\frac{r_{k+1}^j}{1-\rho_2^k}} + \delta},\quad \forall j=1,\cdots,l
    \end{equation}
    其中$\epsilon$是全局学习率，建议默认为 $0.0001$。$\delta$ 一般为小常数 $\sim 10^{-6}$，为了除法的数值稳定性而添加。
\end{definition}
Adam 算法一般认为对超参数的选择比较稳健，并且同样具有较好的效果。

不难发现，以上都是一些一阶的优化方法。还有一些二阶的优化方法，比如牛顿法、拟牛顿法等。但这些方法因为要计算 Hessian 矩阵，从而具有较大的计算成本和内存需求，对深度学习不友好。即使有一些算法，如存储受限的 BFGS (L-BFGS) 算法减缓了这个问题，但仍距离深度学习的要求尚远，更不要说十亿至万亿参数级别的大型模型了。

\section{正则化方法}
在选定了目标函数之后，我们还可以为目标函数添加一些新的项，以满足我们对模型参数的偏好 (这往往意味着在样本以外的数据上也具有较好的泛化能力)。比如说，我希望一个模型的参数，如果一方面能较好地完成任务 (也就是说，使得我们选定的目标函数值较小)，另一方面这些参数不要太大，最好能有很多零，这样我就有机会将那些为零的参数略去，缩小模型规模、减少计算量。

考虑线性模型 $f(\vec{x}) = \vec{w}^T\vec{x}, \vec{x}\in\mathbb{R}^d$，其通过最小均方误差，或者极大似然估计法，得到的目标函数是
\begin{equation}
    J(\vec{w}) = \sum_{i=1}^{m}\abs{y_i - \vec{w}^T\vec{x}_i}_2
\end{equation}
那么我们便可以为目标函数添加权重衰减项
\begin{equation}
    \tilde{J}(\vec{w}) = \sum_{i=1}^{m}\abs{y_i - \vec{w}^T\vec{x}_i}_2 + \alpha \vec{w}^T\vec{w} = J(\vec{w}) + \alpha\Omega(\vec{w})
\end{equation}
这样就相当于鼓励模型采用较小的 $\vec{w}$，因为这样也能使得目标函数较小。在这里，我们引入了一个超参数 $\alpha$，当 $\alpha$ 越大时，意味着我们对 $\vec{w}$ 较小的偏好越严重。当它非常大时，模型就几乎会忽略掉样本，而专注于满足我们的偏好，给出一个具有非常小 $\vec{w}$ 的模型。 

在最大后验估计中，我们曾看到，我们加入的先验分布 $\pi(\vec{w})$，会被转化为目标函数中的一项 $\log\pi(\vec{w})$。特别是，当我们给出先验分布 $\pi(\vec{w})$ 为各分量独立、且方差相同的正态分布 $N(\vec{w}; \vec{\mu},\frac{1}{\alpha}I)$，那么所得到的先验项正是我们上面给出的正则项 $\alpha \vec{w}^T\vec{w}$。事实上，有许多带有正则项的估计方法，可以解释为贝叶斯推断的最大后验估计。毕竟，这些正则项往往对应了我们给模型参数设定的先验信息。不过，也有一些情况是不能对应到最大后验估计推断的，比如有些正则项不能化为某个分布的对数的情况。

在其他模型中，我们还可能考虑其他正则化方法。有时候，也有可能只为部分模型参数添加惩罚。例如，在深度神经网络中，我们往往只对权重 $\vec{w}$ 作惩罚，而不对偏置$b$作惩罚。这是因为精确拟合偏置所需的数据往往比精确拟合权重的数据少得多，所以我们即使不对偏置作正则化，也不会导致很大的方差。下面，我们用 $\theta$ 表示所有参与点估计的参数，而 $\vec{w}$ 表示那些出现在正则项中的参数。

\paragraph{$L^2$ 正则化} 有时，也称为岭回归或者 Tikhonov 正则。其添加的正则项为
\begin{equation}
    \Omega(\theta) = \frac{1}{2}\|\vec{w}\|_2^2
\end{equation}
此时，更新权重为 
\begin{equation}
    \vec{w} = (1-\epsilon\alpha)\vec{w} - \epsilon\nabla_\vec{w} \sum_{i=1}^{m}J(\vec{w}; \vec{x}_i, y_i)
\end{equation}
其中 $\alpha$ 是正则化的超参数。为了深入研究 $L^2$ 正则化的影响，我们考虑不带正则化的最优解 $\vec{w}^\star$，在它附近展开不带正则化的目标函数$\hat{J}(\theta)$，使得
\begin{equation}
    \hat{J}(\theta) = J(\vec{w}^\star) + \frac{1}{2}(\vec{w} - \vec{w}^\star)^T H (\vec{w} - \vec{w}^\star)
\end{equation}
这里 $H$ 是 Hessian 阵。这里没有一阶项，是因为在最优解附近梯度为零。当 $\hat{J}(\theta)$ 取得最小时，其梯度 
\begin{equation}
    \nabla_{\vec{w}}\hat{J}(\vec{w}) = H(\vec{w} - \vec{w}^\star) = 0
\end{equation}
现在，我们往 $\hat{J}_{\vec{w}}$ 的梯度中，添加正则化之后的项：
\begin{equation}
    \alpha\tilde{\vec{w}} + H(\tilde{\vec{w}} - \vec{w}^\star) = 0
\end{equation}
其中 $\tilde{w}$ 是正则化之后的最优解。上面这个等式，只要$\tilde{w}$处于 $\vec{w}^\star$ 附近，使得二阶展开有效，那么就成立。从中可以解出：
\begin{eqnarray}
    \tilde{w} = (H + \alpha I)^{-1} H\vec{w}^\star 
\end{eqnarray}
其中 $I$ 是单位矩阵。我们希望能看到，随着 $\alpha$ 的变化，$\tilde{\vec{w}}$ 的位置是怎样在 $\vec{w}^\star$ 周围运动的，以此来显示 $L^2$ 正则化的效果。为此，我们将 $H$ 进行特征值分解。由于它是半正定的对称阵 (半正定性是由最优解保证的，而 Hessian 阵对于连续可微目标函数而言，本来就是对称阵)，所以 $H = Q\Lambda Q^T$，其中 $Q$ 是特征向量的标准正交基，$\Lambda$ 是特征值组成的对角矩阵。从而 
\begin{eqnarray}
    \tilde{w} = Q(\Lambda + \alpha I)^{-1} \Lambda Q^T \vec{w}^\star 
\end{eqnarray}
可以看到，权重衰减的效果，是沿着由 $H$ 的特征向量所定义的轴，缩放 $\vec{w}^\star$ 的各个分量。设第 $j$ 个分量的特征值为 $\lambda_j$，则该方向上的分量将会变为 
\begin{eqnarray}
    \tilde{w}^j = \frac{\lambda_j}{\lambda_j + \alpha}(w^\star)^j
\end{eqnarray} 
请注意，这里所说的分量，是$\tilde{\vec{w}}$以及 $\vec{w}^\star$ 需要在特征向量对应的标准正交基分解中，所得的第 $j$ 个分量，而不是直接拿第 $j$ 的元素来算。

不难发现，$H$ 的特征值越大，表示在该方向上的损失函数的曲率越大。当增加正则化强度 $\alpha$ 时，这些大特征值对应的方向上，正则化的作用就不明显。而在特征值较小、曲率较小，从而在最优点附近几乎没有什么变化的方向上，$L^2$ 正则化就会将参数在该分量上的权重进行缩减。

\paragraph{$L^1$ 正则化} 对模型参数 $\vec{w}$ 的 $L^1$ 正则化定义为 
\begin{equation}
    \Omega(\theta) = \|\vec{w}\|_{1} = \sum_{j=1}^{d}|w^d|
\end{equation}
此时，正则化的目标函数为 
\begin{equation}
    \tilde{J}(\vec{w}) = \alpha\|\vec{w}\|_1 + J(\vec{w}) 
\end{equation}
对应的梯度为 
\begin{equation}
    \nabla_{\vec{w}}\tilde{J}(\vec{w}) = \alpha \mathrm{sign} (\vec{w}) + \nabla_{\vec{w}}J(\vec{w})
\end{equation}
其中 $\mathrm{sign}$ 函数是对各个分量取符号。可以发现，$L^1$正则化的效果是添加了一项与 $\mathrm{sign}(w^j)$ 同号的常数。这意味着，我们最终不一定能得到 $J(\vec{w})$ 二次近似的直接算数解 (在 $L^2$ 中是可以的)。和分析 $L^2$ 正则时相同的手续，对于模型而言，我们可以设想其在局部最优$\vec{w}^\star$附近，可以进行二阶的泰勒展开：
\begin{equation}
    \nabla_{\vec{w}}\hat{J}(\vec{w}) = H(\vec{w} - \vec{w}^\star)
\end{equation}
并且，考虑到对于 $L^1$ 正则化而言这仍不好处理，我们设想 $H$ 已经是一个对角阵了，其对角元素为 $\lambda_j$，于是 
\begin{equation}
    \hat{J}(\vec{w}) = J(\vec{w}^\star) + \sum_{j=1}^{d}\rbk{\frac{1}{2}\lambda_j(w^j - (w^\star)^j)^2 + \alpha|w^j|}
\end{equation}
这个代价函数的解为 
\begin{equation}
    w^j = \mathrm{sign}((w^\star)^j)\max\rbk{|(w^\star)^j| - \frac{\alpha}{\lambda^j}, 0}
\end{equation}
考虑 $(w^\star)^j$ 的情形，会有两种可能的结果：
\begin{enumerate}
    \item $(w^\star)^j \leq \alpha/\lambda^j$ 的情形，这意味着正则化后目标中的 $w^j=0$。
    \item  $(w^\star)^j > \alpha/\lambda^j$ 的情形，这时参数 $w^j$ 的值会减少一个常数，为 $\alpha/\lambda^j$。
\end{enumerate}
可以看到，对于那些 $H$ 特征值特别大的方向，$L^1$ 正则化只是将 $w$ 略微减少，减少的数值与 $H$ 特征值有关，而且特征值越大，变化得越小，这个效果和 $L^2$ 正则化的效果是类似的。

然而，对于那些 $H$ 特征值很小的地方，如果此时 $(w^\star)^j$ 还比较大，那么 $L^1$ 正则化则会直接把这个分量变成零。这和 $L^2$ 正则化的效果并不相同，因为在那里参数值只会被压缩，但不会被完全抹去。因此，$L^1$ 正则化鼓励模型优化成一个稀疏的解，使得参数中存在很多完全不起作用的参数。

由 $L^1$ 正则化导出的稀疏性质，被广泛用于特征选择 (feature selection) 中。它从可用的特征子集中，选择出有意义的特征，以化简机器学习问题。著名的 LASSO (Least Absolute Shrinkage and Selection Order) 模型，就将 $L^1$ 正则化与线性模型结合，并且使用最小二乘法的代价函数。此时，$L^1$ 正则化就会使得部分子集的权重为零，使其可以安全地忽略。

前面提到，许多正则化策略可以被解释为最大后验估计。例如，$L^2$ 正则化就相当于取正态分布作为先验的最大后验估计。那么，对于 $L^1$ 正则化而言，就相当于取拉普拉斯分布 (指数分布) 作为先验分布的最大后验估计。

\section{约束问题}\label{Sec 约束问题} 

考虑经过参数范数正则化的代价函数 
\begin{eqnarray}
    \tilde{J}(\theta) = J(\theta) + \alpha\Omega(\vec{w})
\end{eqnarray}
如果对参数 $\theta$ 有所约束，例如使得 $\Omega(\vec{w}) < k$，那么最简单的办法便是将约束考虑在内后对梯度下降算法进行修改。例如，我们先作无约束的梯度下降，然后再把结果投影到约束上。但另一种约束问题的经典方法是基于拉格朗日乘子法的所谓 KKT (Karush-Kuhn-Tucker) 方法。

\begin{theorem}[Karush-Kuhn-Tucker (KKT)]
    对于约束问题，目标函数为函数 $f(\theta)$，并且具有等式约束 $h_i(\theta) = 0$ 以及不等式约束 $g_j(\theta) \leq 0$而言，我们有广义拉格朗日函数 
    \begin{equation}
        L(\theta, \lambda, \mu) = f(\theta) + \sum_{i}\lambda_i h_i(\theta) + \sum_j \mu_j g_j(\theta),\quad \lambda_i, \mu_j \geq 0
    \end{equation}
    则当 $\theta^*$ 为 $f(\theta)$ 的局部极小值点时，满足 
    \begin{equation}
        \nabla_\theta L(\theta^*, \lambda_i, \mu_j) = 0
    \end{equation}
    并且，对于不等式约束 $g_j(\theta)$，要么该约束是激活的 ($g(\theta^*) = 0$)，要么它是未激活的 $g(\theta^*) < 0$。在约束未激活的情形下，其对应的拉格朗日乘子 $\mu_j = 0$。
\end{theorem}

广义拉格朗日函数的有效性可以通过以下事实给出。假设给定某个 $\theta$。如果 $\theta$ 违反原始问题的约束条件，也就是存在 $g_j(\theta) > 0$ 或者 $h_i(\theta) \neq 0$，那么此时
\begin{equation}
    \max_{\lambda,\mu}L(\theta, \lambda, \mu) = \max_{\lambda, \mu}\rbk{f(\theta) + \sum_{i}\lambda_i h_i(\theta) + \sum_j \mu_j g_j(\theta)} \to \infty
\end{equation}
毕竟，如果有某个 $j$ 使得约束 $g_j(\theta) > 0$，则对于任意的 $\epsilon$，可令 $\mu_j = \epsilon / g_j(\theta)  + 1$，从而使得 $\max_{\lambda,\mu}L(\theta, \lambda, \mu) > \epsilon$。对于 $i$ 以及 $h_i(\theta)$ 所面临的情况同理。所以，要想让关于 $\theta$ 的函数 $\max_{\lambda,\mu}L(\theta, \lambda, \mu)$ 存在，就只能让所有的 $\lambda_i, \mu_j = 0$，从而
\begin{equation}
    \max_{\lambda,\mu}L(\theta, \lambda, \mu) = f(\theta)
\end{equation}
因而与原来带约束的优化问题等价。

可以看到，KKT 为我们描述了一个带不等约束的最优点所具有的性质，这也为我们找到这个最优点提供了契机。而拉格朗日函数梯度为零的条件，对应于这样的事实——我们手里有三种方程，第一种是 $f(\theta) = C$，第二种是 $g(\theta) = 0$，第三种是 $h(\theta) = 0$。当 $C$ 不是最优解时，我们期望能找到许多 $g(\theta) = 0$ 并且 $h_j(\theta) \leq 0$ 的点，满足 $f(\theta) = C$，在几何上就表现为曲面相交。但当 $C$ 逐渐趋向于最优解时，只有 (局部) 最优点满足条件，那么此时在几何上就表现为曲面相切。

考虑 KKT 方法之后，则新的代价函数为 
\begin{equation}
    L(\theta,\alpha) = J(\theta) + \alpha(\Omega(\vec{w}) - k)
\end{equation}
为了让参数满足条件 $\Omega(\vec{w}) \leq k$，必须在训练中也调整 $\alpha$，使得当 $\Omega(\vec{w}) > k$ 时，$\alpha$ 会变大，以加重惩罚，而当 $\Omega(\vec{w}) < k$ 时，$\alpha$ 会变小，以减轻惩罚。

除了原始的带约束最优化问题之外，还有其对偶问题。这种对偶的做法在感知机和支持向量机中将会遇到。我们考虑问题 $\max_{\lambda,\mu}\min_{\theta}L(\theta,\lambda,\mu)$，它称为广义拉格朗日函数的极大极小问题。我们定义最优值
\begin{equation}
    d^* = \max_{\lambda,\mu}\min_{\theta}L(\theta,\lambda,\mu)
\end{equation}
为对偶问题的值。

\begin{theorem}
    如果原始问题和对偶问题都有最优值，则
    \begin{equation}
        d^* = \max_{\lambda,\mu}\min_{\theta}L(\theta,\lambda,\mu)\leq \min_{\theta}\max_{\lambda,\mu} L(\theta,\lambda,\mu) = p^*,\quad \lambda_i,\mu_j > 0
    \end{equation}
    其中 $p^*$ 是原始问题中，广义拉格朗日函数的最优值。
\end{theorem}
\begin{proof}
    我们有对于任意的 $\theta,\lambda,\mu$， 
    \begin{equation}
        \min_{\theta} L(\theta,\lambda,\mu)\leq L(\theta,\lambda,\mu) \leq \max_{\lambda,\mu} L(\theta,\lambda,\mu)
    \end{equation}
    上面的不等式告诉我们，左边的式子在任何情况下都不大于右边的式子。所以，左边的式子即使取了最大值，也不大于右边的式子的最小值：
    \begin{equation}
        \max_{\lambda,\mu}\min_{\theta}L(\theta,\lambda,\mu)\leq \min_{\theta}\max_{\lambda,\mu} L(\theta,\lambda,\mu)
    \end{equation}\qed 
\end{proof}

在某些条件下，对偶问题和原始问题的解相同，从而可以把解决原始问题转换为解决对偶问题。
\begin{theorem}
    假设函数 $f(\theta)$ 和 $g_j(\theta)$ 是凸函数，而 $h_i(\theta)$ 是仿射函数，并且假设不等式约束 $g_j(\theta)$ 是严格可行的 (就是说存在 $\theta$ 使得 $g_j(\theta) < 0$)，那么存在 $\theta^*, \lambda^*, \mu^*$，使得 $\theta^*$ 是原始问题的解，而 $\lambda^*, \mu^*$ 是对偶问题的解，且
    \begin{equation}
        p^* = d^* = L(\theta^*, \lambda, \mu)
    \end{equation}
    其中 $p^*$ 是原始问题的拉格朗日函数最优值，$d^*$ 是对偶问题拉格朗日函数的最优值。
\end{theorem}
而且 
\begin{theorem}[KKT]
    假设函数 $f(\theta)$ 和 $g_j(\theta)$ 是凸函数，而 $h_i(\theta)$ 是仿射函数，并且假设不等式约束 $g_j(\theta)$ 是严格可行的 (就是说存在 $\theta$ 使得 $g_j(\theta) < 0$)，那么 $\theta^*, \lambda^*, \mu^*$ 分别为原始问题和对偶问题的解的充要条件是问题和解满足 KKT 条件。
\end{theorem}

为了理解 KKT 方法和对偶问题，我们来做两道例题。我们求解
\begin{equation}
    \min_{x,y} f(x,y) = x^2 + 4y^2,\quad s.t.\ x^2 + y^2 - 1 \leq 0
\end{equation}
首先我们构造广义拉格朗日函数
\begin{equation}
    L(x,y,\lambda) = x^2 + y^2 + \lambda(x^2 + y^2 - 1)
\end{equation}
其中 $\lambda$ 是拉格朗日乘子，对应于不等式约束。KKT 条件包含以下几个部分：
\begin{enumerate}
    \item 梯度为零 (Stationarity)：
        \begin{equation}
            \begin{aligned}
                \pdv{L}{x} &= 2x + 2\lambda x = 0
                \pdv{L}{y} &= 8y + 2\lambda x = 0
            \end{aligned}
        \end{equation}
    \item 原始可行性 (Primal feasibility)
        \begin{equation}
            x^2 + y^2 - 1 \leq 0
        \end{equation}
    \item 对偶可行性 (Dual feasibility)
        \begin{equation}
            \lambda \geq 0
        \end{equation}
    \item 互补松弛性 (Complementary Slackness)
        \begin{equation}
            \lambda(x^2 + y^2 - 1) = 0
        \end{equation}
\end{enumerate}
有四个解：
\begin{equation}
    \begin{cases}
        x = -1\\
        y = 0\\
        \lambda = -1
    \end{cases}
    \quad 
    \begin{cases}
        x = 0\\
        y = -1\\
        \lambda = -4
    \end{cases}
    \quad 
    \begin{cases}
        x = 0\\
        y = 1\\
        \lambda = -4
    \end{cases}
    \quad 
    \begin{cases}
        x = 1\\
        y = 1\\
        \lambda = -1
    \end{cases}
\end{equation}

很不幸，四组解全都不满足对偶可行性。不过，我们也可以借机观察一下，对偶可行性以及互补松弛性是如何发挥作用的。我们先排除掉两个不是最小值的点，而只留下是最小值的两个点。然后，我们发现它们都满足约束条件 $x^2 + y^2 \leq 1$。具体来说，它们满足等式 $x^2 + y^2 = 1$，也就是说它们是边界上的点。如果我们将约束条件从不等式改成等式，立刻可以发现点 $(-1, 0)$ 和 $(1, 0)$ 就是等式约束下的最小值点。

但它们全都不满足对偶可行性，也就不满足 KKT 条件。我们应当使用 KKT 条件来解题，考虑互补松弛性，发现 $\lambda = 0$ 也是一种可行的解。这就意味着，约束条件并不显式地进入拉格朗日函数中，从而与寻找全局最小值等价。考虑到原函数 $f(x, y) = x^2 + 4y^2$ 是个开口向上的抛物面，所以最小值在 $(0, 0)$ 处取得。不难发现，它满足约束条件，从而是问题的解。

从这道题中，我们可以看出 KKT 的各个条件的作用：
\begin{enumerate}
    \item 梯度为零和等式约束的拉格朗日乘子法相同；
    \item 原始可行性把约束条件抄了一遍；
    \item 对偶可行性比较关键，它给出了我们验证解是否合法的途径；
    \item 互补松弛性则告诉我们，只有两种情况：约束生效，此时最优解在边界上，当等式约束处理；约束不生效，此时最优解不在边界上，当全局最优化问题处理。
\end{enumerate}

还可以反过来，考虑约束为 $x^2 + y^2 \geq 1$ 的情况。显然，此时最优解就会在边界上取得了，因为往边界外走得越远，目标函数就会越大。此时拉格朗日函数为 
\begin{equation}
    L = x^2 + 4y^2 - \lambda(x^2 + y^2 - 1)
\end{equation}
这里要注意到符号的变化，因为 KKT 条件中，使用的不等式约束是 $\leq$，而我们的约束是 $\geq$，所以要在两边乘以 $-1$。不难得到，此时最终结果是 $(-1, 0)$ 以及 $(1, 0)$。

我们继续考虑约束为 $x^2 + y^2 \geq 1$ 时的对偶问题。此时，我们需要求
\begin{equation}
    \max_{\lambda}\min_{x,y}L(x,y,\lambda),\quad \lambda > 0
\end{equation}
首先，我们求在给定不同的 $\lambda$下，$L$的最小值。如果这里直接求导的话，会发现最小值在 
\begin{equation}
    \pdv{L}{x} = 2x - 2\lambda x,\quad \pdv{L}{y} = 8y - 2\lambda y
\end{equation}
处取得。然后，我们考虑让它们等于零，得到 $x = 0$ 且 $y = 0$ (因为 $\lambda > 0$)。但这个极值其实是取不到的，因为它不满足约束条件。所以，我们只能慢慢分析约束条件下，不同 $\lambda$ 会面临哪些结果。
\begin{enumerate}
    \item $\lambda > 4$，此时 $L(x, y, \lambda)$ 最小值是发散的 
    \item $\lambda = 4$，此时 $y^2$ 被抵消了，但 $x^2$ 仍在，最小值还是发散的 
    \item $1 < \lambda < 4$，此时是个双曲面，最小值仍是发散的 
    \item $\lambda = 1$，此时 $x^2$ 被抵消了，留下了 $3y^2 + 1$，最小值在 $y=1$ 处取得，此时 $L$ 的最小值为 $\lambda$
    \item $0 < \lambda < 1$，此时是个开口向上的抛物面，最小值为 $\lambda$ 
\end{enumerate}
因而，可以看到
\begin{equation}
    \min_{x,y}L(x,y,\lambda) = \begin{cases}
        -\infty,\quad \lambda > 1\\
        \lambda,\quad 0 < \lambda \leq 1
    \end{cases}
\end{equation}
在所有这些值里面，最大的显然是
\begin{equation}
    \max_{\lambda}\min_{x,y}L(x,y,\lambda) = 1
\end{equation}
这和我们在原问题中所得到的最优值是一致的。

另一方面，我们也经常会使用显式约束，也就是前面介绍的，在梯度下降的过程中，把计算的结果投影到满足约束的面上。这种方法有时能避免出现局部极小，并且避免在训练过程中出现正反馈。

\paragraph{欠定问题} 正则化也可以用来解决欠定问题。这是基于一个简单的想法，因为很多问题可能具有无穷多组解 (例如，参数比样本还多的线性回归)。而正则化则对这些解作了进一步的筛选，使得只有一个解满足我们的需求。这实际上就是把欠定问题转化为良定义的问题。

\section{计算微分}
在定义好了目标函数 $J(\theta;\vec{x}_i, y_i)$ 后，我们想要求得最优化的解，往往就需要计算其导数 $\nabla_{\theta}J(\theta;\vec{x}_i, y_i)$。这对于我们在优化方法一节中介绍的各种方法，包括一阶的和二阶的，都成立。那么，如何在计算机中计算一个函数的导数？在数值计算方法中，可以用数值差分来代替微分。但这不是机器学习中最优化问题的普遍情况，因为给定模型和目标函数之后，导函数的形式也随之给定了，因而我们理应能计算导数的解析解。而如果用差分来代替微分，则要考虑到，我们赖以差分的样本往往相当有限，很多时候并不足以让我们计算差分。

如果用纸笔来计算导数，这当然是容易的，遵循一般的求导法则来算就可以。问题在于如何让计算机来计算导数？尤其是，我们需要给定目标函数的形式，然后让计算机来自动给出导函数的形式，最后带入数值计算。一种想法是使用符号计算系统，但这对于大规模但是单纯只计算导数的任务来说，开销太大了。

我们需要使用计算图的语言来描述这个过程。
\begin{definition}[计算图]
    计算图被定义为一个有向无环图 (Directed Acyclic Graph, DAG) $G = (V, E)$，其中 $V$ 是节点的集合，$E$ 是边的集合。节点 $V$ 中包含了所有单元，每个节点 $v\in V$ 代表一个操作 (例如加法、乘法、函数)，或者一个变量。边 $E\subset V\times V$ 包含了所有的边，表示数据流动的方向。 如果存在一条从节点 $u$ 到节点 $v$ 的边，即 $(u, v)\in E$，则表示 $u$ 的输出是 $v$ 的输入。对于没有入边，只有出边的节点，则表示数据的输入点。对于只有入边，没有出边的节点，则表示数据的输出点。
\end{definition}
考虑线性模型，则计算图可以表示为：
\begin{enumerate}
    \item 输入节点 $x^j$，这个节点只有输出边，没有内置计算函数
    \item 权重节点 $w^j$，这个节点只有输出边，没有内置计算函数
    \item 乘法节点 $w^jx^j$，这个节点有两个输入边，且内置的计算函数是乘法
    \item 加法节点 $\sum_{j}w^jx^j$，这个节点有 $d$ 个输入边，且内置的计算函数是加法 (作为一个具有不定个数自变量的函数)
    \item 输出节点 $y$，这个节点只有输入边，没有内置计算函数
\end{enumerate}

有了计算图之后，就可以使用图的方法来计算各参量的导函数了。更深的计算图，对应于嵌套层数更高的复合函数。对于复合函数 $z = f(y) = f(g(x))$而言，这依赖于求导的链式法则：
\begin{equation}
    \pdv{z}{x^j} = \sum_{i}\pdv{z}{y^i}\pdv{y^i}{x^j}
\end{equation}
可以看到，如果我们把 $z$ 当作目标函数，$x^j$ 当作参数，那么我们在优化方法中，要想得到 $x^j$ 处目标函数相对于其的导数 $\pdv{z}{x^j}$，就必须先计算 $\pdv{z}{y^i}$ 以及 $\pdv{y^i}{x^j}$，然后将二者作相乘、相加。考虑到，当我们输入 $x^j$ 时，此时 $y^i = g(x^j)$ 的值，以及导数值，就可以计算出来了。再进一步，就可以计算出此处 $\pdv{z}{y^i}$ 的值。再最后，即可算出复合函数的导数值，从而知道我们应该往哪里移动。

以线性模型为例，看看使用计算图和复合函数求导，求解参数导数的过程：
\begin{enumerate}
    \item 根据模型，构建从样本输入$x_i^j$、模型参数$w^j$到模型输出$\hat{y}_i$的计算图
    \item 模型输出$\hat{y}_i$与样本值$y_i$二者决定了目标函数$J(\hat{y}_i, y_i) = J(w^j; x_i^j, y_i)$的计算图，它相当于第一步中的计算图的末尾又添加了一个操作用于计算目标函数。
    \item 根据目标函数的计算图$J(w^j; x_i^j, y_i)$，计算当前输入$x_i^j$以及参数 $w^j$ 下，各参数 $w^j$ 处，目标函数的导数 $\pdv{J(w^j; x_i^j, y_i)}{w^j}$：
    \begin{itemize}
        \item 根据目标函数的计算图 $J(\hat{y}_i, y_i)$，计算当前 $\hat{y}_i$ 以及 $y_i$ 处的目标函数导数 $\pdv{J(\hat{y}_i, y_i)}{\hat{y}_i}$ 以及 $\pdv{J(\hat{y}_i, y_i)}{y_i}$。但由于样本值 $y_i$ 算是输入的一部分，与当前的参数 $w^j$ 无关，所以后续我们不会用到它。
        \item 导数 $\pdv{J(\hat{y}_i, y_i)}{\hat{y}_i}$ 中，$\hat{y}_i$ 是模型参数 $w^j$ 和样本输入 $x_i^j$ 的函数。所以，我们需要继续计算 $\pdv{\hat{y}_i}{w^j}$ 以及 $\pdv{\hat{y}_i}{x_i^j}$。但由于样本输入 $x_i^j$ 也算是输入的一部分，与当前参数 $w^j$ 无关，所有后续我们也不会用到它。
        \item  我们发现，$\pdv{\hat{y}_i}{w^j}$ 是直接作用的，而不是复合函数，它可以直接计算。而计算图中的其它分支，都不能连通到 $w^j$。因此，计算导数 $\pdv{J(w^j; x_i^j, y_i)}{w^j}$ 所需的材料已经准备好了，直接相乘、相加即可。
    \end{itemize}
    \item 至此，我们计算了目标函数在当前输入以及参数状态下，对参数的偏导数。
\end{enumerate}
可以观察到，求导的链条是从尾部的目标函数，逐渐传导至头部的输入的，所以又称为反向传播。如果线性模型不止一层 (对于线性模型来说意义不大，但对于其他非线性的模型来说就有所不同了)，那么计算复合函数导数的链条还要继续从后往前传递，完成反向传播的过程。

对于线性模型而言，目标函数的计算图中，从参数到目标函数的路径是唯一的。但当模型层数变多、拓扑结构变复杂之后就未必如此。这时，我们需要遍历所有从目标函数到某个参数的路径，将每条路径下的复合函数求导值都加起来，才能最终完成导数的计算。换句话说，对于 $z = z(x,y) = z(x(w), y(w), w)$ 而言，我们有 
\begin{equation}
    \dv{z}{w} = \pdv{z}{x}\pdv{x}{w} + \pdv{z}{y}\pdv{y}{w} + \pdv{z}{w}
\end{equation}
这一个性质对于那些深层的神经网络模型来说比较重要。

在实际计算中，会碰到很多可能会重复计算的量。例如，对于上面的式子，当我们要计算 $\pdv{z}{x}$ 时，我们需要知道 $x$ 的值。而 $x$ 是 $w$ 的函数，所以这是可以临时计算的。但我们往往要先算出 $z$，然后再进行反向传播，这意味着 $x$ 已经被计算过一次了。如果我们存储空间很大，那么我们可以缓存好 $x$，到时候就可以直接用了，不用重复计算。毕竟如果不缓存的话，复合函数嵌套层数多一层，它就要多重复一次之前的计算，计算量指数增长。但如果存储空间十分受限，则的确可以用时间换空间。

代数表达式和计算图都对符号或者不具有特定值的变量进行操作。这些代数或者基于图的表达式被称为符号表示。在计算中，我们需要用一个特定的数值来代替网络的符号输入。有两种方法来实现这一点：
\begin{enumerate}
    \item 符号到数值的微分，例如 Torch。它首先构建一个计算图，该图表示模型的计算流程，但不包含具体的数值。当需要进行反向传播时，它接受具体的数值输入，并在这些输入值上执行计算图，同时计算梯度。它只有模型对应的计算图。它每次执行时都会根据具体的数值，重新计算梯度。
    \item 符号微分，例如 TensorFlow。它不仅包含模型的计算流程，还包含梯度计算的流程。因此，梯度计算本身也是计算图的一部分，可以使用与原始模型相同的语言和结构来描述 (或者说，梯度也是独立的计算图)。其优点在于，可以一次性构建完整的计算图，包括梯度计算，然后在需要时使用具体的数值执行这个图。
\end{enumerate}

% 一些反向传播算法，采用计算图和一组用于图的输入的数值，然后返回在这些输入值处梯度的一组数值。这种方法被称为符号到数值的微分，例如 Torch 就是这样的。而另一种则是采用计算图以及添加一些额外的节点到计算图中，这些额外的节点提供了我们所需导数的符号描述，这是 TensorFlow 所采用的方法。这种方法的主要优点是导数可以使用与原始表达式相同的语言来描述，因为导数只是另外一张计算图。



% \section{结构化概率模型}
% 机器学习的算法经常会涉及到在非常多的随机变量上的概率分布。通常，这些概率分布涉及到的直接相互作用都是介于非常少的变量之间的。使用单个函数来描述整个联合概率分布是非常低效的。

% 我们可以把概率分布分解成许多因子的乘积形式，而不是使用单一的函数来表示概率分布。例如，假设我们有三个随机变量$X,Y,Z$，其中$X$影响$Y$的取值，$Y$影响$Z$的取值。但是$X$和$Z$在给定$Y$时是条件独立的，也就是说
% \begin{equation}
% P(X,Z|Y)=P(X|Y)P(Z|Y)
% \end{equation}
% 我们可以把全部三个变量的概率分布重新表示为两个变量的概率分布相乘的形式：
% \begin{equation}
% P(X,Y,Z)=P(Y,Z|X)P(X)=P(X)P(Y|X)P(Z|Y)
% \end{equation}
% 这种分解可以极大地减少用来描述一个分布的参数数量。每个因子使用的参数数目是它的变量数目的指数倍。这意味着，如果我们能够找到一种使得每个因子分布具有更少变量的分解方法， 就能极大地降低表示联合分布的成本。

% 我们可以用图(Graph)来描述这种分解。这种图叫做结构化概率模型(Structured probabilistic model)或者图模型。分为有向的和无向的两种，两种图模型都使用图$\mathcal{G}$，其中每个节点对应一个随机变量，连接两个随机变量的边意味着概率分布可以表示成这两个随机变量之间的直接作用。

% 有向模型使用带有向边的图，对于分布中的每一个随机变量$X_i$，包含一个影响因子，这个组成$X_i$条件概率的影响因子叫做$X_i$的父节点，记为$Pa_{\mathcal{G}}(X_i)$。这样，随机向量$X$的概率分布可以写为
% \begin{equation}
% P(X)=\prod_{i}P(X_i|Pa_{\mathcal{G}(X_i)})
% \end{equation}

% 无向模型使用带有无向边的图，它们将分解表示成一组函数；不像有向模型那样，这些函数通常不是任何类型的概率分布。在图$\mathcal{G}$中任何满足两两之间有边连接的顶点的集合被称为团。无向模型中的每个团$\mathcal{C}^{(i)}$都伴随一个因子$\phi^{(i)}(\mathcal{C}^{(i)})$。这些因子仅仅是函数，而不是概率分布。每个因子的输出都是非负的，但不要求归一化。随机变量的联合概率与所有这些因子的乘积成比例：
% \begin{equation}
% P(X)=\frac{1}{Z}\prod_{i}\phi^{(i)}(\mathcal{C}^{(i)})
% \end{equation}
% 其中$Z$就是配分函数。

% \section{支持向量机}
% 给定训练样本集合$D=\{(x_1,y_1),\cdots,(x_m,y_m)\}, y_i\in\{-1,1\}$，分类学习最基本的想法就是基于训练集$D$在样本空间中找到一个划分超平面
% \begin{equation}
% \sum_{i}w^ix^i+b=0
% \end{equation}
% 将不同类别的样本分开。其中$w^i$是法向量，$b$是位移项；我们把这个超平面就记为$(w^i,b)$。样本空间中的任何点$x^i$到超平面$(w^i,b)$的距离可以写为
% \begin{equation}
% r=\dfrac{\sum_{i}|w^ix^i+b|}{\sqrt{\sum_{j}(w^j)^2}}
% \end{equation}
% 显然，对于样本空间中的点$x^i$，$\sum w^ix^i+b$的符号就决定了其分类。

% 如果我们选取$w^i$，使得两类样本离超平面的距离都足够远，就能达到最安全的效果。我们令
% \begin{equation}
% \begin{cases}
% \sum_{i}w^ix_j^i + b\geq 1,\quad &y_j=1\\
% \sum_{i}w^ix_j^i + b\leq -1,\quad &y_j=-1
% \end{cases}
% \end{equation}
% 其中，距离超平面最近的几个样本使得等号成立，这几个样本就叫做支持向量(Support vector)。定义间隔(margin)为两个不同类的支持向量到超平面的距离之和：
% \begin{equation}
% \gamma = \dfrac{2}{\sqrt{\sum_{i}(w^i)^2}}
% \end{equation}

% 想要找到最大间隔的划分超平面，也就是要找到能满足约束的参数$w^i$和$b$使得$\gamma$最大，也就是
% \begin{equation}
% \max_{w^i,b}=\frac{2}{\sqrt{\sum_{i}(w^i)^2}},\quad s.t.\ (\sum_{i}w^ix_j^i+b)y_j\geq 1,\quad j=1,\cdots,m
% \end{equation}

% 对于线性不可分的样本(比如异或)，我们可以考虑将样本从一个原始空间映射到更高维的空间，使得样本在该特征空间内线性可分。令$\phi(x)$表示将$\vec{x}$映射后的特征向量，于是在特征空间中划分超平面所对应模型可以表示为
% \begin{equation}
% f(\vec{x})=\vec{w}\cdot \phi(\vec{x})+b
% \end{equation}
% 从而问题转化为
% \begin{equation}
% \min_{\vec{w},b} \|\vec{w}\|,\quad s.t.\ (\vec{w}\cdot \phi(\vec{x}_j)+b)y_j\geq 1,\quad j=1,\cdots,m
% \end{equation}

% 一般而言，在求解该问题的时候，会遇到求$\phi(\vec{x}_i)\cdot\phi(\vec{x}_j)$的问题。然而特征空间维度可能很高，所以直接计算这个内积一般是困难的。因此，我们考虑把先选定特征空间，再计算$\phi(\vec{x})$内积的过程，转化为事先选定$\phi(\vec{x})$的内积，然后用此来表示特征空间的路子。这样选定的内积(类似于二元线性函数的度量矩阵)就是核函数：
% \begin{equation}
% \kappa(\vec{x}_i,\vec{x}_j)=\phi(\vec{x}_i)\cdot\phi(\vec{x}_j)
% \end{equation}
% 我们要求这样的度量矩阵是半正定的。常见的核函数可以选为
% \begin{enumerate}
% 	\item 线性核。 $\kappa(\vec{x}_i,\vec{x}_j)=\vec{x}_i\cdot\vec{x}_j$
% 	\item 多项式核。$d$是多项式次数。 $\kappa(\vec{x}_i,\vec{x}_j)=(\vec{x}_i\cdot\vec{x}_j)^d$
% 	\item 高斯核 $\kappa(\vec{x}_i,\vec{x}_j)=\exp\left(-\frac{1}{2\sigma^2}\|\vec{x}_i-\vec{x}_j\|^2\right)$
% 	\item 拉普拉斯核。把高斯核指数的次数改为一次。
% 	\item Sigmoid核。$\kappa(\vec{x}_i,\vec{x}_j)=\tanh(\beta\vec{x}_i\cdot\vec{x}_j+\theta)$
% \end{enumerate}

% \section{贝叶斯分类器}
% 假设有$N$种可能的类别标记，即$\mathcal{Y}=\{c_1,\cdots,c_N\}$，$\lambda_{ij}$是将一个标记为$c_j$的样本误分类为$c_i$所产生的损失。基于后验概率$P(c_i|\vec{x})$可获得将样本$\vec{x}$分类为$c_i$所产生的期望损失(也叫条件风险)：
% \begin{equation}
% R(c_i|\vec{x})=\sum_{j=1}^N \lambda_{ij}P(c_j|\vec{x})
% \end{equation}
% 我们的任务是寻找一个判定准则$h:\mathcal{X}\to\mathcal{Y}$以最小化总体风险
% \begin{equation}
% R(h)=ER(h(\vec{x})|\vec{x})=E\sum_{j=1}^N \lambda_{ij}P(h(\vec{x})|\vec{x})
% \end{equation}
% 显然，如果对于每个样本$h$大批么干嘛最小化条件风险$R(h(\vec{x})|\vec{x})$，则总体风险也能最小化。这就产生了贝叶斯判定准则：为了最小化总体风险，只需要在每个样本上选择那个能使条件风险$R(c|\vec{x})$最小的类别标记，也就是
% \begin{equation}
% h^*(\vec{x})=\arg\min_{c\in\mathcal{Y}}R(c|\vec{x})
% \end{equation}
% 此时，$h^*$称为贝叶斯最优分类器，与之对应的总体风险$R(h^*)$称作贝叶斯风险。

% 作为例子，取目标为最小化分类错误率，则误判损失$\lambda_{ij}$可以写为$1-\delta_{ij}$，此时条件风险是
% \begin{equation}
% R(c_i|\vec{x})=\sum_{j=1}^N(1-\delta_{ij})P(c_j|\vec{x})=\sum_{j=1}^N P(c_j|\vec{x})-P(c_i|\vec{x})=1-P(c_i|\vec{x})
% \end{equation}
% 于是最小化分类错误率的贝叶斯最优分类器是
% \begin{equation}
% h^*(\vec{x})=\arg\max_{c\in\mathcal{Y}}P(c|\vec{x})
% \end{equation}
% 也就是说，对于每一个样本$\vec{x}$，选择能使后验概率$P(c|\vec{x})$最大的类别标记。

% 然而，后验概率不好获得。根据贝叶斯估计一章的手续，需要先有先验概率$\pi(c)$，然后用此概率产生一系列样本$X_i$，这些样本的分布服从$P(X_i|c)$，然后根据贝叶斯公式，后验概率是
% \begin{equation}
% P(c|\vec{x})=\dfrac{\pi(c)P(X_i|c)}{\sum_{c}\pi(c)P(X_i|c)}
% \end{equation}
% 实际运用中，可以直接建模$P(c|\vec{x})$，这叫做判别式模型，比如说SVM、决策树、神经网络；也可以对联合分布$P(\vec{x},c)$进行建模，这叫做生成式模型，典型的有极大似然估计。

% 事实上，$P(c|\vec{x})$不好获得的原因是无法从有限的样本中直接估计得到。为了避开这个障碍，可以使用朴素贝叶斯分类器，它假设对于已知的类别，所有属性都相互独立。于是
% \begin{equation}
% P(c|\vec{x})=\frac{P(c)P(\vec{x}|c)}{P(\vec{x})}=\frac{P(c)}{P(\vec{x})}\prod_{i=1}^{d}P(x^i|c)
% \end{equation}
% 由于对于所有类别，$P(\vec{x})$都相同，因此贝叶斯判定准则是
% \begin{equation}
% h_{nb}(\vec{x})=\arg\max_{c\in\mathcal{Y}}\prod_{i=1}^d P(x^i|c)
% \end{equation}
% 而$P(c)$和$P(x^i|c)$都由样本的频率来代替概率了。

